package com.fanshuai.algorithms.branch;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 01背包问题（01 knapsack problem）：一共有N件物品，第i件物品的重量为w[i]，价值为v[i]。
 * 在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
 *
 * 使用分支限界法求解
 */
public class Bag {
    static class BagNode {
        public int i; //物品索引
        public int weight;  //遍历到当前节点的重量
        public int v;  //遍历到当前节点的价值
    }

    /**
     * 0-1背包问题
     * @param weight  物品重量
     * @param v    物品价值
     * @param W    背包总重量
     * @return
     */
    public static int knapsackBranch(int[] weight, int[] v, int W) {
        int n = weight.length;
        int maxV = Integer.MIN_VALUE; //最大价值

        Queue<BagNode> queue = new ArrayDeque<>();
        BagNode node0 = new BagNode();
        node0.i = 0;
        node0.weight = 0;
        node0.v = 0;
        queue.add(node0);

        while (!queue.isEmpty()) {
            BagNode node = queue.poll();
            if (node.v > maxV) {
                maxV = node.v;
            }

            BagNode node1 = new BagNode(); //1分支
            BagNode node2 = new BagNode(); //0分支

            if (node.i + 1 <= n) {
                if (node.weight + weight[node.i] <= W) { //1分支
                    node1.i = node.i + 1;
                    node1.weight = node.weight + weight[node.i];
                    node1.v = node.v + v[node.i];

                    queue.add(node1);
                }

                node2.i = node.i + 1;  //0分支
                node2.weight = node.weight;
                node2.v = node.v;
                queue.add(node2);
            }
        }

        return maxV;
    }

    public static void main(String[] args) {
        int[] weight = {1, 2, 3, 4, 10};
        int[] v = {20, 11, 22, 100, 1000};
        int W = 11;

        int[] weight2 = {1, 2, 3, 4, 10};
        int[] v2 = {20, 11, 22, 100, 100};
        int W2 = 12;

        System.out.println(knapsackBranch(weight, v, W));
        System.out.println(knapsackBranch(weight2, v2, W2));
    }
}
